On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

On the threshold problem for Latin boxes

Let m ≤ n ≤ k. An m × n × k 0‐1 array is a Latin box if it contains exactly m n ones, and has at most one 1 in each line. As a special case, Latin boxes in which m = n = k are equivalent to Latin squares. Let be the distribution on m × n × k 0‐1 arrays where each entry is 1 with probability p, independently of the other entries. The threshold question for Latin squares asks when contains a Latin square with high probability. More generally, when does support a Latin box with high probability? Let ε > 0. We give an asymptotically tight answer to this question in the special cases where n = k and , and where n = m and . In both cases, the threshold probability is . This implies threshold results for Latin rectangles and proper edge‐colorings of K_n,n.     

小度数图的邻点可区别全染色

本文研究了最大度为3 且没有相邻最大度的图的邻点可区别全染色. 利用边剖分的方法, 构造了此类图更为一般的情形, 得到了它们的邻点可区别全色数的上界. 目前, 未找到最大度为3 的图且它的邻点可区别全色数是6. 本文的结果部分地回答了这个问题.     

小度数图的邻点可区别全染色

本文研究了最大度为3且没有相邻最大度的图的邻点可区别全染色.利用边剖分的方法,构造了此类图更为一般的情形,得到了它们的邻点可区别全色数的上界.目前,未找到最大度为3的图且它的邻点可区别全色数是6.本文的结果部分地回答了这个问题.     

Edge colorings of graphs embeddable in a surface of low genus

In this paper, by using the Discharging Method, we show that any graph with maximum degree Δ 8 that is embeddable in a surface Σ of characteristic χ(Σ) 0 is class one and any graph with maximum degree Δ 9 that is embeddable in a surface Σ of characteristic χ(Σ) = − 1 is class one. For surfaces of characteristic 0 or −1, these results improve earlier results of Mel'nikov.     

Finding Δ(Σ) for a surface σ of characteristic χ(Σ) = −5

For each surface Σ, we define Δ(Σ) = max{Δ(G)|Gis a class two graph of maximum degree Δ(G) that can be embedded in Σ}. Hence, Vizing's Planar Graph Conjecture can be restated as Δ(Σ) = 5 if Σ is a plane. In this paper, we show that Δ(Σ) = 9 if Σ is a surface of characteristic χ(Σ) = ?5. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:148‐168, 2011     

On splittable colorings of graphs and hypergraphs

The notion of a split coloring of a complete graph was introduced by Erd?s and Gyárfás [ 7 ] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)‐split coloring problem of [ 7 ] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002     

On a modification of a problem of Bialostocki, Erd?s, and Lefmann

For positive integers m and r, one can easily show there exist integers N such that for every map Δ:{1,2,…,N}→{1,2,…,r} there exist 2m integers

x₁<?<x_m<y₁<?<y_m,